#include "ix_node_handle.h"

/**
 * @brief 在当前node中查找第一个>=target的key_idx
 *
 * @return key_idx，范围为[0,num_key)，如果返回的key_idx=num_key，则表示target大于最后一个key
 * @note 返回key index（同时也是rid index），作为slot no
 */
int IxNodeHandle::lower_bound(const char *target) const {
    // Todo:
    // 查找当前节点中第一个大于等于target的key，并返回key的位置给上层
    // 提示: 可以采用多种查找方式，如顺序遍历、二分查找等；使用ix_compare()函数进行比较
    int num_key = this->page_hdr->num_key;// 获取当前结点的键的数量
    int key_idx = 0;// 初始化键的索引
    // 二分查找
    int first = 0,last=num_key-1,middle;// 初始化二分查找的首尾索引和中间索引
    char *src;// 用于存储键值的指针
    while(first<last)// 在首尾索引之间进行循环，直到找到满足条件的位置
    {
        middle = (first+last)/2;// 计算中间索引
        src = get_key(middle);// 获取中间位置的键值
        if(ix_compare(src,target,file_hdr->col_type,file_hdr->col_len)<0)// 比较键值和目标键值
        {
            first=middle+1;// 如果中间键小于目标键值，更新首索引
            key_idx=first;// 更新键的索引
        }
        else
        {
            last=middle;// 更新尾索引
            key_idx=last;// 更新键的索引
        }
    }
    if(key_idx==num_key-1)// 如果键的索引等于最后一个键
    {
        if(ix_compare(get_key(num_key-1),target,file_hdr->col_type,file_hdr->col_len)<0)// 比较最后一个键和目标键值
        {
            return num_key;// 返回键的数量，表示目标大于最后一个键
        }
    }
    return key_idx;// 返回键的索引，表示未找到大于或等于目标键值的键
}

/**
 * @brief 在当前node中查找第一个>target的key_idx
 *
 * @return key_idx，范围为[1,num_key)，如果返回的key_idx=num_key，则表示target大于等于最后一个key
 * @note 注意此处的范围从1开始
 */
int IxNodeHandle::upper_bound(const char *target) const {
    // Todo:
    // 查找当前节点中第一个大于target的key，并返回key的位置给上层
    // 提示: 可以采用多种查找方式：顺序遍历、二分查找等；使用ix_compare()函数进行比较
    int num_key = this->page_hdr->num_key;// 获取当前结点的键的数量
    int key_idx = 0;// 初始化键的索引
    // 二分查找
    int first = 0,last=num_key-1,middle;// 初始化二分查找的首尾索引和中间索引
    char *src;// 用于存储键值的指针
    while(first<last)// 在首尾索引之间进行循环，直到找到满足条件的位置
    {
        middle = (first+last)/2;// 计算中间索引
        src = get_key(middle);// 获取中间位置的键值
        if(ix_compare(src,target,file_hdr->col_type,file_hdr->col_len)<=0)// 比较键值和目标键值
        {
            first=middle+1;// 如果中间键小于或等于目标键值，更新首索引
            key_idx=first;// 更新键的索引
        }
        else
        {
            last=middle;// 更新尾索引
            key_idx=last;// 更新键的索引
        }
    }
    if(key_idx==num_key-1)// 如果键的索引等于最后一个键
    {
        if(ix_compare(get_key(num_key-1),target,file_hdr->col_type,file_hdr->col_len)<=0)// 比较最后一个键和目标键值
        {
            return num_key;// 返回键的数量，表示目标大于等于最后一个键
        }
    }
    return key_idx;// 返回键的索引，表示未找到大于目标键值的键
}

/**
 * @brief 用于叶子结点根据key来查找该结点中的键值对
 * 值value作为传出参数，函数返回是否查找成功
 *
 * @param key 目标key
 * @param[out] value 传出参数，目标key对应的Rid
 * @return 目标key是否存在
 */
bool IxNodeHandle::LeafLookup(const char *key, Rid **value) {
    // Todo:
    // 1. 在叶子节点中获取目标key所在位置
    // 2. 判断目标key是否存在
    // 3. 如果存在，获取key对应的Rid，并赋值给传出参数value
    // 提示：可以调用lower_bound()和get_rid()函数。
    int key_idx = lower_bound(key);// 使用 lower_bound 查找第一个 >= 目标 key 的键的索引
    if(key_idx==this->page_hdr->num_key)// 如果键的索引等于键的数量，说明目标 key 大于最后一个键
    {
        return false;// 返回未找到
    } 
    char* src = get_key(key_idx);// 获取找到的键值
    if(ix_compare(src,key,file_hdr->col_type,file_hdr->col_len)!=0)// 比较键值和目标键值
    {
        return false;// 如果键值不相等，返回未找到
    }
    *value = get_rid(key_idx);// 将找到的键值对应的 Rid 作为传出参数
    return true;// 返回找到了目标 key
}

/**
 * 用于内部结点（非叶子节点）查找目标key所在的孩子结点（子树）
 * @param key 目标key
 * @return page_id_t 目标key所在的孩子节点（子树）的存储页面编号
 */
page_id_t IxNodeHandle::InternalLookup(const char *key) {
    // Todo:
    // 1. 查找当前非叶子节点中目标key所在孩子节点（子树）的位置
    // 2. 获取该孩子节点（子树）所在页面的编号
    // 3. 返回页面编号
    int rid_idx = upper_bound(key);// 使用 upper_bound 查找第一个 > 目标 key 的键的索引
    if(rid_idx!=0)// 如果索引不为 0
    {
        rid_idx-=1;// 减去 1 来获取应该查找的孩子节点的索引
    }
    return ValueAt(rid_idx);// 获取相应索引处的孩子节点（子树）的存储页面编号
}

/**
 * @brief 在指定位置插入n个连续的键值对
 * 将key的前n位插入到原来keys中的pos位置；将rid的前n位插入到原来rids中的pos位置
 *
 * @param pos 要插入键值对的位置
 * @param (key, rid) 连续键值对的起始地址，也就是第一个键值对，可以通过(key, rid)来获取n个键值对
 * @param n 键值对数量
 * @note [0,pos)           [pos,num_key)
 *                            key_slot
 *                            /      \
 *                           /        \
 *       [0,pos)     [pos,pos+n)   [pos+n,num_key+n)
 *                      key           key_slot
 */
void IxNodeHandle::insert_pairs(int pos, const char *key, const Rid *rid, int n) {
    // Todo:
    // 1. 判断pos的合法性
    // 2. 通过key获取n个连续键值对的key值，并把n个key值插入到pos位置
    // 3. 通过rid获取n个连续键值对的rid值，并把n个rid值插入到pos位置
    // 4. 更新当前节点的键数量
    int num_key = page_hdr->num_key;// 获取当前键值对数量
    if(pos<0||pos>num_key)// 检查插入位置是否合法
    {
        return;// 如果位置不合法，直接返回
    }
    for(int i=num_key-1;i>=pos;i--)
    {
        memmove(get_key(i+n),get_key(i),file_hdr->col_len);// 将后面的键移到正确的位置以腾出空间
        memmove(get_rid(i+n),get_rid(i),sizeof(Rid));// 将后面的Rid移到正确的位置以腾出空间
    }
    for(int i=0;i<n;i++)
    {
        memmove(get_key(pos+i),key+i*file_hdr->col_len,file_hdr->col_len);// 插入新的键
        memmove(get_rid(pos+i),rid+i,sizeof(Rid));// 插入新的Rid
    }
    page_hdr->num_key += n;// 插入新的Rid
}

/**
 * @brief 用于在结点中的指定位置插入单个键值对
 */
void IxNodeHandle::insert_pair(int pos, const char *key, const Rid &rid) { insert_pairs(pos, key, &rid, 1); };

/**
 * @brief 用于在结点中插入单个键值对。
 * 函数返回插入后的键值对数量
 *
 * @param (key, value) 要插入的键值对
 * @return int 键值对数量
 */
int IxNodeHandle::Insert(const char *key, const Rid &value) {
    // Todo:
    // 1. 查找要插入的键值对应该插入到当前节点的哪个位置
    // 2. 如果key重复则不插入
    // 3. 如果key不重复则插入键值对
    // 4. 返回完成插入操作之后的键值对数量
    int key_idx = lower_bound(key);// 查找要插入的键值对的位置
    if(key_idx<page_hdr->num_key&&ix_compare(get_key(key_idx),key,file_hdr->col_type,file_hdr->col_len)==0)// 如果已经存在相同的键，不进行插入，直接返回键值对数量
    {
        return page_hdr->num_key;
    }
    insert_pair(key_idx,key,value);// 插入新的键值对
    return page_hdr->num_key;// 返回键值对数量
}

/**
 * @brief 用于在结点中的指定位置删除单个键值对
 *
 * @param pos 要删除键值对的位置
 */
void IxNodeHandle::erase_pair(int pos) {
    // Todo:
    // 1. 删除该位置的key
    // 2. 删除该位置的rid
    // 3. 更新结点的键值对数量
    int num_key = page_hdr->num_key;// 获取当前键值对数量
    if(pos<0||pos>=num_key)
    {
        return;// 如果指定位置无效，不进行删除
    }
    // 通过 memmove 将指定位置的键和值从后面的键值对覆盖过来，实现删除
    memmove(get_key(pos),get_key(pos+1),(num_key-pos-1)*file_hdr->col_len);
    memmove(get_rid(pos),get_rid(pos+1),(num_key-pos-1)*sizeof(Rid));
    page_hdr->num_key -= 1;// 更新键值对数量
}

/**
 * @brief 用于在结点中删除指定key的键值对。函数返回删除后的键值对数量
 *
 * @param key 要删除的键值对key值
 * @return 完成删除操作后的键值对数量
 */
int IxNodeHandle::Remove(const char *key) {
    // Todo:
    // 1. 查找要删除键值对的位置
    // 2. 如果要删除的键值对存在，删除键值对
    // 3. 返回完成删除操作后的键值对数量
    int key_idx = lower_bound(key);// 查找指定 key 在节点中的位置
    if(key_idx<page_hdr->num_key&&ix_compare(get_key(key_idx),key,file_hdr->col_type,file_hdr->col_len)==0)// 如果找到了匹配的 key
    {
        erase_pair(key_idx);// 使用 erase_pair 函数删除该位置的键值对
    }
    return page_hdr->num_key;// 返回删除键值对后的键值对数量s
}

/**
 * @brief 由parent调用，寻找child，返回child在parent中的rid_idx∈[0,page_hdr->num_key)
 *
 * @param child
 * @return int
 */
int IxNodeHandle::find_child(IxNodeHandle *child) {
    int rid_idx;
    for (rid_idx = 0; rid_idx < page_hdr->num_key; rid_idx++) {
        if (get_rid(rid_idx)->page_no == child->GetPageNo()) {
            break;
        }
    }
    assert(rid_idx < page_hdr->num_key);
    return rid_idx;
}

/**
 * @brief used in internal node to remove the last key in root node, and return the last child
 *
 * @return the last child
 */
page_id_t IxNodeHandle::RemoveAndReturnOnlyChild() {
    assert(GetSize() == 1);
    page_id_t child_page_no = ValueAt(0);
    erase_pair(0);
    assert(GetSize() == 0);
    return child_page_no;
}